package leetcode_classic150;


import model.ListNode;
import model.Node;
import model.TreeNode;

import java.util.*;

public class Demo4 {


    // 141. 环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode slow = head, fast = head.next;

        while (fast != null && fast.next != null && slow != fast) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow == fast;
    }




    // 2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;

        ListNode res = new ListNode();
        ListNode tail = res;
        while (l1 != null || l2 != null || carry > 0) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }

            ListNode node = new ListNode(carry % 10);
            tail.next = node;
            tail = node;
            carry /= 10;
        }

        tail.next = null;
        return res.next;
    }



    // 21. 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        ListNode head = new ListNode();
        ListNode tail = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        if (list1 != null) tail.next = list1;
        if (list2 != null) tail.next = list2;
        return head.next;
    }



    // 138. 随机链表的复制
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Map<Node,Node> map = new HashMap<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }

        for (Node cur = head; cur != null; cur = cur.next) {
            Node node = map.get(cur);
            node.next = map.get(cur.next);
            node.random = map.get(cur.random);
        }
        return map.get(head);
    }



    // 19. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) count++;

        ListNode ret = new ListNode();
        ret.next = head;
        ListNode prev = ret, cur = head;
        for (int i = 0; i < count - n; i++) {
            prev = cur;
            cur = cur.next;
        }

        prev.next = cur.next;
        return ret.next;
    }



    // 82. 删除排序链表中的重复元素 II
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode ret = new ListNode();
        ret.next = head;
        ListNode prev = ret;
        for (ListNode cur = head; cur != null; ) {
            // 可能存在多个连续的重复节点
            while (cur != null && cur.next != null && cur.val == cur.next.val) {
                int tmp = cur.val;
                while (cur != null && cur.val == tmp) cur = cur.next;
            }
            prev.next = cur;
            prev = cur;
            if (cur != null) cur = cur.next;
        }
        return ret.next;
    }



    // 61. 旋转链表
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;

        ListNode cur = head;
        int count = 1;
        for (; cur.next != null; cur = cur.next) count++;   // 此时cur是链表的最后一个结点
        if ((k %= count) == 0) return head;

        ListNode prev = new ListNode();
        prev.next = head;
        ListNode ret = head;
        for (int i = 0; i < count - k; i++) {
            prev = ret;
            ret = ret.next;
        }

        prev.next = null;
        cur.next = head;
        return ret;
    }



    // 226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return root;

        TreeNode leftTree = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(leftTree);
        return root;
    }



    //101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        return childIsSymmetric(root.left, root.right);
    }
    private boolean childIsSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return childIsSymmetric(left.right, right.left) && childIsSymmetric(left.left, right.right);
    }


    // 112. 路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        targetSum -= root.val;

        if (root.left == null && root.right == null && targetSum == 0) return true;
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }


    // 105. 从前序与中序遍历序列构造二叉树
    private int pos;
    Map<Integer,Integer> hash;      // 记录元素和下标的映射关系

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        hash = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) hash.put(inorder[i], i);
        return buildTreeBypreOrder(preorder, inorder, 0, preorder.length - 1);
    }

    private TreeNode buildTreeBypreOrder(int[] preorder, int[] inorder, int left, int right) {
        if (left > right) return null;
        TreeNode root = new TreeNode(preorder[pos++]);
        int index = hash.get(root.val);

        root.left =  buildTreeBypreOrder(preorder, inorder, left, index - 1);
        root.right = buildTreeBypreOrder(preorder, inorder, index + 1, right);
        return root;
    }



    // 106. 从中序与后序遍历序列构造二叉树
    private int pos2;
    Map<Integer,Integer> hash2;

    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        pos = inorder.length - 1;
        hash = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) hash.put(inorder[i], i);
        return buildTreeByPostorder(inorder, postorder, 0, inorder.length - 1);
    }
    private TreeNode buildTreeByPostorder(int[] inorder, int[] postorder, int left, int right) {
        if (left > right) return null;
        TreeNode root = new TreeNode(postorder[pos--]);
        int index = hash.get(root.val);

        root.right = buildTreeByPostorder(inorder, postorder, index + 1, right);
        root.left = buildTreeByPostorder(inorder, postorder, left, index - 1);
        return root;
    }




    // 124. 二叉树中的最大路径和
    private int ret = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ret;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;

        // 若子树路径和小于0，则不加入路径(置为0)
        int left = dfs(root.left), right = dfs(root.right);
        left = Math.max(left, 0);
        right = Math.max(right, 0);

        ret = Math.max(ret, root.val + left + right);
        // 父结点的子路径组成只能由 当前结点 + 左右子路径中的任意一条组成
        return root.val + Math.max(left, right);
    }



    // 236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }



    // 222. 完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }


    // 199. 二叉树的右视图
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if (root == null) return ret;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            ret.add(q.peek().val);
            for (int sz = q.size(); sz > 0; sz--) {
                TreeNode t = q.poll();
                if (t.right != null) q.offer(t.right);
                if (t.left != null) q.offer(t.left);
            }
        }
        return ret;
    }



    // 102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for (int sz = q.size(); sz > 0; sz--) {
                TreeNode t = q.poll();
                tmp.add(t.val);
                if (t.left != null) q.offer(t.left);
                if (t.right != null) q.offer(t.right);
            }
            ret.add(tmp);
        }
        return ret;
    }



    // 103. 二叉树的锯齿形层序遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int flag = 1;    // 1为从左到右，-1为从右到左
        while (!q.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for (int sz = q.size(); sz > 0; sz--) {
                TreeNode t = q.poll();
                if (flag > 0) tmp.add(t.val);
                else tmp.addFirst(t.val);
                if (t.left != null) q.offer(t.left);
                if (t.right != null) q.offer(t.right);
            }
            flag *= -1;
            ret.add(tmp);
        }
        return ret;
    }



    // 530. 二叉搜索树的最小绝对差
    private int ret3 = Integer.MAX_VALUE, prev3 = -1;

    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;

        getMinimumDifference(root.left);
        if (prev3 != -1) ret = Math.min(ret, Math.abs(root.val - prev3));
        prev3 = root.val;
        getMinimumDifference(root.right);

        return ret;
    }



    // 230. 二叉搜索树中第K小的元素
    int count, ret4 = -1;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inOrder(root);
        return ret4;
    }

    private void inOrder(TreeNode root) {
        if(root == null) return;

        if(count > 0) inOrder(root.left);
        if(--count == 0) {
            ret4 = root.val;
        }
        if(count > 0) inOrder(root.right);
    }



    // 98. 验证二叉搜索树
    TreeNode prev = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        if(!isValidBST(root.left)) return false;
        if(prev != null && prev.val >= root.val) return false;
        prev = root;
        return isValidBST(root.right);
    }



    // 200. 岛屿数量
    int row, col;
    int[] dx = new int[]{0,0,1,-1};
    int[] dy = new int[]{1,-1,0,0};
    public int numIslands(char[][] grid) {
        // 深度优先遍历 dfs
        row = grid.length; col = grid[0].length;

        int ret = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
    private void dfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';

        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }



    // 130. 被围绕的区域
//    private int row, col;
    public void solve(char[][] board) {
        row = board.length;
        col = board[0].length;

        // 1. 对四周为 'O' 的结点进行dfs，并将'O' 替换为 '.'
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[row - 1][j] == 'O') dfs2(board, row - 1, j);
        }
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][col - 1] == 'O') dfs2(board, i, col - 1);
        }

        // 2. 将 '.' 替换为 'O'， 将 'O' 替换为 'X'
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '.') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
    }
//    private final int[] dx = new int[]{0,0,1,-1};
//    private final int[] dy = new int[]{1,-1,0,0};
    private void dfs2(char[][] board, int i, int j) {
        board[i][j] = '.';

        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'O') {
                dfs2(board, x, y);
            }
        }
    }




    // 433. 最小基因变化
    public int minMutation(String startGene, String endGene, String[] bank) {
        // 1. 统计基因库中出现的所有有效基因
        Set<String> bankSet = new HashSet<>();
        for (String s : bank) bankSet.add(s);
        if (!bankSet.contains(endGene)) return -1;

        // 2. 统计所有变化过的有效基因
        Set<String> emergenceGene = new HashSet<>();
        emergenceGene.add(startGene);

        // 3. 存放当前变化的基因
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);

        // 4. 尝试 bfs
        int ret = 0;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                String cur = q.poll();
                if (cur.equals(endGene)) return ret;

                for (String s : bank) {
                    char[] arr = cur.toCharArray();
                    for (int i = 0; i < 8; i++) {
                        if (cur.charAt(i) != s.charAt(i)) {
                            arr[i] = s.charAt(i);
                            break;
                        }
                    }
                    String tmp = new String(arr);
                    // 判断替换后的字符串是否在基因库中，且之前没有出现过
                    if (bankSet.contains(tmp) && !emergenceGene.contains(tmp)) {
                        q.offer(tmp);
                        emergenceGene.add(tmp);
                    }
                }
            }
            ret++;
        }
        return -1;
    }


    // 274. H 指数
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int left = 0, right = n - 1, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) right = mid;
            else left = mid + 1;
        }
        return citations[left] > 0 ? n - left : 0;
    }



    // 224. 基本计算器
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();
        char[] ss = s.toCharArray();
        numStack.push(0);
        opStack.push('+');

        for (int i = 0, n = ss.length; i < n; ) {
            if (ss[i] >= '0' && ss[i] <= '9') {
                // 提取数字
                int num = 0;
                while (i < n && ss[i] >= '0' && ss[i] <= '9') {
                    num = num * 10 + ss[i++] - '0';
                }
                // 与前一个数作计算
                char op = opStack.pop();
                int front = numStack.pop();
                if (op == '-') numStack.push(front - num);
                else numStack.push(front + num);
            } else if (ss[i] == '(') {
                numStack.push(0);       // 不管是 +- 都当作双目运算符，在前面加一个0
                i++;
                // 如果括号后不是 -，则需要入栈 + 作为 0 的运算符
                while (i < n && ss[i] == ' ') i++;
                if (ss[i] != '-') opStack.push('+');
            } else if (ss[i] == ')'){
                // 将数字栈的两个数作运算,注意 num1和num2的前后关系
                Integer num2 = numStack.pop(), num1 = numStack.pop();
                char op = opStack.pop();
                if (op == '-') numStack.push(num1 - num2);
                else numStack.push(num1 + num2);
                i++;
            } else if (ss[i] == ' ') i++;
            else opStack.push(ss[i++]);
        }
        return numStack.pop();
    }

    public static void main1(String[] args) {
        int[][] board = new int[6][];
        board[0] = new int[]{-1,-1,-1,-1,-1,-1};
        board[1] = new int[]{-1,-1,-1,-1,-1,-1};
        board[2] = new int[]{-1,-1,-1,-1,-1,-1};
        board[3] = new int[]{-1,35,-1,-1,13,-1};
        board[4] = new int[]{-1,-1,-1,-1,-1,-1};
        board[5] = new int[]{-1,15,-1,-1,-1,-1};
        snakesAndLadders(board);
    }
    public static int snakesAndLadders(int[][] board) {
        int n = board.length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{n - 1, 0});
        boolean[][] vis = new boolean[n][n];    // 已经访问过的结点不能再次访问
        vis[n - 1][0] = true;

        int step = 0;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                int flag = i % 2 == (n - 1) % 2 ? 1 : -1;  // 下标为[i][j]的元素, 当 i%2 == n%2时 flag->1, 否则 flag->-1
                if (i == 0 && j == n - 1) return step;

                for (int k = 0; k < 6; k++) {
                    if ((i % 2 == (n - 1) % 2 && j == n - 1) || (i % 2 == n % 2 && j == 0)) {       // 换方向，换行
                        i--;
                        flag = -flag;
                    } else {
                        j += flag;
                    }
                    System.out.println(i + " " + j);
                    if (vis[i][j]) continue;

                    vis[i][j] = true;
                    q.offer(new int[]{i, j});
                    if (board[i][j] != -1) {        // 发生传送
                        int x = n - 1 - board[i][j] / n;
                        int rest = board[i][j] % n;
                        int y = x % 2 == n % 2 ? n - rest : rest - 1;
                        if (!vis[x][y]) {
                            vis[x][y] = true;
                            q.offer(new int[]{x, y});
                        }
                    }

                }
            }
            step++;
        }
        return -1;
    }
}
